<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(A卷,200分)- 二进制差异数（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>对于任意两个正整数A和B&#xff0c;定义它们之间的<strong>差异值和相似值</strong>&#xff1a;<br /><strong>差异值&#xff1a;</strong>A、B转换成二进制后&#xff0c;对于二进制的每一位&#xff0c;对应位置的bit值不相同则为1&#xff0c;否则为0&#xff1b;<br /><strong>相似值&#xff1a;</strong>A、B转换成二进制后&#xff0c;对于二进制的每一位&#xff0c;对应位置的bit值都为1则为1&#xff0c;否则为0&#xff1b;<br /> 现在有n个正整数A0到A&#xff08;n-1&#xff09;&#xff0c;问有多少(i, j) (0&lt;&#61;i&lt;j&lt;n&#xff09;&#xff0c;Ai和Aj的差异值大于相似值。<br /> 假设A&#61;5&#xff0c;B&#61;3&#xff1b;则A的二进制表示101&#xff1b;B的二进制表示011&#xff1b;<br /> 则A与B的差异值二进制为110&#xff1b;相似值二进制为001&#xff1b;<br /> A与B的差异值十进制等于6&#xff0c;相似值十进制等于1&#xff0c;满足条件。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>一个n接下来n个正整数</p> 
<p><strong>数据范围</strong>&#xff1a;1&lt;&#61;n&lt;&#61;10^5&#xff0c;1&lt;&#61;A[i]&lt;2^30</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>满足差异值大于相似值的对数</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">4<br /> 4 3 5 2</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">4</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">满足条件的分别是(0,1)(0,3)(1,2)(2,3)&#xff0c;共4对。</td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>题目描述中&#xff0c;</p> 
<p>A&#xff0c;B差异值其实就是A和B二进制的按位异或运算&#xff0c;即A ^ B。</p> 
<p>A&#xff0c;B相似值其实就是A和B二进制的按位与运算&#xff0c;即A &amp; B。</p> 
<p></p> 
<p>因此&#xff0c;如果本题使用暴力法求解&#xff0c;则逻辑非常简单&#xff0c;如下</p> 
<pre><code class="language-javascript">// 入参arr是用例第二行输入对应的数组
function getResult(arr) {
  const ans &#61; [];
  for (let i &#61; 0; i &lt; arr.length; i&#43;&#43;) {
    for (let j &#61; i &#43; 1; j &lt; arr.length; j&#43;&#43;) {
      const diff &#61; arr[i] ^ arr[j];
      const simi &#61; arr[i] &amp; arr[j];
      if (diff &gt; simi) {
        ans.push([i, j]);
      }
    }
  }
  console.log(ans);
  return ans.length;
}</code></pre> 
<p>但是1&lt;&#61;n&lt;&#61;10^5&#xff0c;而上面算法复杂度达到了O(n^2)&#xff0c;因此会超时。</p> 
<p>对于1&lt;&#61;n&lt;&#61;10^5&#xff0c;算法时间复杂度应该至少控制在O(n)。</p> 
<p></p> 
<p>因此&#xff0c;我们需要发现规律&#xff0c;而不是暴力求解。</p> 
<p>本题的规律其实很容易发现&#xff0c;那就是看A&#xff0c;B的最高位1是否处于相同位&#xff0c;如果相同&#xff0c;比如</p> 
<p>A&#xff1a;1010</p> 
<p>B&#xff1a;1100</p> 
<p>那么差异值就是0110&#xff0c;相似值就是1000&#xff0c;可以发现&#xff0c;A,B最高位的1&#xff0c;在按位异或运算下被换成0&#xff0c;在按位与的运算下&#xff0c;变成了1&#xff0c;因此这种情况下&#xff0c;相似值必然大于差异值&#xff0c;不符合要求。</p> 
<p>如果A&#xff0c;B的最高位1不处于相同位&#xff0c;比如</p> 
<p>A&#xff1a;1010</p> 
<p>B&#xff1a;0110</p> 
<p>那么差异值就是1100&#xff0c;相似值就是0010&#xff0c;可以发现&#xff0c;A&#xff0c;B的最高位不同&#xff0c;因此按位异或运算下被换成了1&#xff0c;而按位与运算下变成了0&#xff0c;因此这种情况下&#xff0c;差异值必然大于相似值&#xff0c;符合要求。</p> 
<p></p> 
<p>有了以上规律&#xff0c;我们可以统计出&#xff0c;每个数的最高位1处于哪一位&#xff0c;最高位1所处位数相同的数之间无法组合&#xff0c;最高位1所处位数不同的数之间可以组合。</p> 
<p>这里我们可以借助&#xff0c;Number.prototype.toString(radix)方法来求出每一个数的二进制形式字符串&#xff0c;由于该方法不会补足前导0&#xff0c;比如Number(6).toString(2)的结果为&#xff1a;110&#xff0c;而不是0000 0110这种带前导0的形式。</p> 
<p>因此我们可以直接将Number(6).toString(2)结果110的字符串长度当成其最高位1所处的位数。</p> 
<p>按此逻辑&#xff0c;我们就可以将最高位1位数相同的数统计到一起了&#xff0c;然后双重for求统计数之间的乘积之和即可。</p> 
<p></p> 
<p>另外&#xff0c;我们需要注意的是&#xff1a;0和1 这两个二进制数的长度都是1&#xff0c;但是“0”却没有最高位1&#xff0c;因此要和“1”区别开来。</p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JavaScript算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61;&#61; 2) {
    const arr &#61; lines[1].split(&#34; &#34;).map(Number);
    console.log(getResult(arr));
    lines.length &#61; 0;
  }
});

function getResult(arr) {
  // highBit是一个数组&#xff0c;由于题目说给定的A[i]取值小于2^30&#xff0c;因此我们可以定义一个30长度的数组&#xff0c;其元素含义是&#xff0c;比如highBit[i]代表最高位1处于第i位的数的个数
  // let highBit &#61; new Array(30).fill(0);
  let highBit &#61; new Array(60).fill(0); // 经网友反馈这里长度定义为60得100%通过率
  for (let a of arr) {
    const bin &#61; Number(a).toString(2);
    const len &#61; bin.length; // 数的二进制形式字符串&#xff08;无前导0&#xff09;的长度&#xff0c;就是该数二进制最高位1所处位数
    // 将“0”和“1”区别开来
    if (bin &#61;&#61; &#34;0&#34;) {
      highBit[0]&#43;&#43;;
    } else {
      highBit[len]&#43;&#43;;
    }
  }

  // 排除统计个数为0的情况
  highBit &#61; highBit.filter((d) &#61;&gt; d);

  let ans &#61; 0;
  for (let i &#61; 0; i &lt; highBit.length; i&#43;&#43;) {
    for (let j &#61; i &#43; 1; j &lt; highBit.length; j&#43;&#43;) {
      ans &#43;&#61; highBit[i] * highBit[j];
    }
  }

  return ans;
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    int n &#61; sc.nextInt();

    int[] arr &#61; new int[n];
    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
      arr[i] &#61; sc.nextInt();
    }

    System.out.println(getResult(arr));
  }

  public static int getResult(int[] arr) {
    // highBit是一个数组&#xff0c;由于题目说给定的A[i]取值小于2^30&#xff0c;因此我们可以定义一个30长度的数组&#xff0c;其元素含义是&#xff0c;比如highBit[i]代表最高位1处于第i位的数的个数
    //    int[] highBit &#61; new int[30];
    int[] highBit &#61; new int[60]; // 经网友反馈&#xff0c;这里长度改为60可得100%通过率

    for (int a : arr) {
      String bin &#61; Integer.toBinaryString(a);
      int len &#61; bin.length(); // 数的二进制形式字符串&#xff08;无前导0&#xff09;的长度&#xff0c;就是该数二进制最高位1所处位数

      // 将“0”和“1”区别开来
      if (&#34;0&#34;.equals(bin)) {
        highBit[0]&#43;&#43;;
      } else {
        highBit[len]&#43;&#43;;
      }
    }

    int ans &#61; 0;
    for (int i &#61; 0; i &lt; highBit.length; i&#43;&#43;) {
      for (int j &#61; i &#43; 1; j &lt; highBit.length; j&#43;&#43;) {
        ans &#43;&#61; highBit[i] * highBit[j];
      }
    }

    return ans;
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
n &#61; int(input())
arr &#61; list(map(int, input().split()))


# 算法入口
def getResult(arr):
    # highBit是一个数组&#xff0c;由于题目说给定的A[i]取值小于2^30&#xff0c;因此我们可以定义一个30长度的数组&#xff0c;其元素含义是&#xff0c;比如highBit[i]代表最高位1处于第i位的数的个数
    # highBit &#61; [0] * 30
    highBit &#61; [0] * 60  # 经网友反馈这里长度改为60可得100%通过率
    for a in arr:
        binStr &#61; format(a, &#39;b&#39;)
        length &#61; len(binStr)  # 数的二进制形式字符串&#xff08;无前导0&#xff09;的长度&#xff0c;就是该数二进制最高位1所处位数

        # 将一位二进制数“0”和“1”区别开来
        if binStr &#61;&#61; &#34;0&#34;:
            highBit[0] &#43;&#61; 1
        else:
            highBit[length] &#43;&#61; 1

    # 排除统计个数为0的情况
    highBit &#61; list(filter(lambda d: d &gt; 0, highBit))

    ans &#61; 0
    for i in range(len(highBit)):
        for j in range(i &#43; 1, len(highBit)):
            ans &#43;&#61; highBit[i] * highBit[j]

    return ans


# 算法调用
print(getResult(arr))
</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>